#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 510;

// 邻接矩阵存图，distance数组存储距离，st数组存储是否已经加入最短路内
// 稠密图用零阶矩阵的原因是便于存储距离
int g[N][N];
int dist[N], n, m;
bool st[N];

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    for (int i = 1; i <= n; ++i)
    {
        // 先找到放入最短路集合中的最小节点位置
        int j = -1;
        for (int t = 1; t <= n; ++t)
            if (!st[t] && (j == -1 || dist[t] < dist[j]))
                j = t;
        // 如果已经找到j了，直接返回
        // if(j == n) return dist[j];
        // 标记已经是最短路了
        st[j] = true;
        // 用找到的j来跟新剩下的所有节点
        for (int t = 1; t <= n; ++t)
            dist[t] = min(dist[t], dist[j] + g[j][t]);
    }
    if (dist[n] == 0x3f3f3f3f)
        return -1;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // 先将临界矩阵中的初始值都设置成正无穷
    // 如果有重边，保留最短的一条边即可
    memset(g, 0x3f, sizeof g);
    cin >> n >> m;
    // 存图
    for (int i = 0; i < m; ++i)
    {
        int a, b, d;
        cin >> a >> b >> d;
        g[a][b] = min(g[a][b], d);
    }
    int t = dijkstra();
    cout << t << endl;

    return 0;
}